package com.kevin.Code.Tree;

import java.util.HashMap;

/**
 * @author Vinlee Xiao
 * @Classname ConstructBinaryTreeFromInorderandPostorderTraversal
 * @Description Leetcode 106. 从中序与后序遍历序列构造二叉树 思路同Leetcode 105
 * @Date 2022/1/4 10:22
 * @Version 1.0
 */
public class ConstructBinaryTreeFromInorderandPostorderTraversal {


    int postIndex;

    /**
     * 思路对了一半
     * 后序遍历的最后一个节点为根节点
     * 基础题目和之前的从中序和前序遍历中构造二叉树思路相同
     *
     * @param inorder
     * @param postorder
     * @return
     */
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        //用于存储中序遍历根节点的位置
        HashMap<Integer, Integer> inorderHashMap = new HashMap<>();
        int len = inorder.length;
        for (int i = 0; i < len; i++) {
            inorderHashMap.put(inorder[i], i);
        }
        //索引
        postIndex = len - 1;

        TreeNode root = dfs(inorder, postorder, 0, len - 1, inorderHashMap);

        return root;
    }

    /**
     * @param inorder        中序遍历数组
     * @param postorder      后续遍历数组
     * @param inorderLeft
     * @param inorderRight
     * @param inorderHashMap
     * @return
     */
    public TreeNode dfs(int[] inorder, int[] postorder, int inorderLeft, int inorderRight, HashMap<Integer, Integer> inorderHashMap) {
        //递归中止条件
        if (inorderLeft > inorderRight) {
            return null;
        }

        int inorderRoot = inorderHashMap.get(postorder[postIndex]);
        TreeNode root = new TreeNode(postorder[postIndex]);

        postIndex--;

        root.right = dfs(inorder, postorder, inorderRoot + 1, inorderRight, inorderHashMap);
        root.left = dfs(inorder, postorder, inorderLeft, inorderRoot - 1, inorderHashMap);

        return root;
    }
}
